package com.xsherl.leetcode.solution;

import java.util.Arrays;

public class InterleavingString {

    /**
     * 假设 s3 是由 s1 和 s2 交叉而来的，那么 s3[1:n] 一定可以被s1[1:x]和s2[1:y]交叉而来
     * 所以得出状态转移方程:
     *  dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int x = s1.length();
        int y = s2.length();
        int z = s3.length();
        if (x + y != z){
            return false;
        }
        boolean[][] dp = new boolean[x + 1][y + 1];
        dp[0][0] = true;
        for (int i = 1; i <= x; ++i) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }
        for (int j = 1; j <= y; ++j) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }
        for (int i = 1; i <= x; ++i){
            for (int j = 1; j <= y; ++j){
                char c = s3.charAt(i + j - 1);
                dp[i][j] = s1.charAt(i - 1) == c && dp[i - 1][j]
                        || s2.charAt(j - 1) == c && dp[i][j - 1];
            }
        }
        return dp[x][y];
    }

    public static void main(String[] args) {
        String s1 = "aabcc";
        String s2 = "dbbca";
        String s3 = "aadbbcbcac";
        boolean interleave = new InterleavingString().isInterleave(s1, s2, s3);
        System.out.println(interleave);
    }

}
